// 题目描述
// 611. 有效三角形的个数
// 难度
// 中等
// 508
// 给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
//   示例 1:
// 输入: nums = [2,2,3,4]
// 输出: 3
// 解释:有效的组合是:
// 2,3,4 (使用第一个 2)
// 2,3,4 (使用第二个 2)
// 2,2,3
// 示例 2:
// 输入: nums = [4,2,3,4]
// 输出: 4
//   提示:
// 1 <= nums.length <= 1000
// 0 <= nums[i] <= 1000
// 通过次数90,597提交次数168,671
// https://leetcode.cn/problems/valid-triangle-number/

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function (nums) {
  const len = nums.length
  if (len < 3) {
    return 0
  }

  nums.sort((a, b) => a - b)

  const helper = (start, target) => {
    let left = start
    let right = len - 1
    while (left <= right) {
      const mid = left + Math.floor((right - left) / 2)
      const cur = nums[mid]
      if (cur === target) {
        right = mid - 1
      } else if (cur < target) {
        left = mid + 1
      } else if (cur > target) {
        right = mid - 1
      }
    }

    if (right === start - 1 || nums[right] >= target) {
      return 0
    }

    return right - start + 1
  }

  let ans = 0
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      ans += helper(j + 1, nums[i] + nums[j])
    }
  }

  return ans
}

console.log(
  triangleNumber(
    [24, 3, 82, 22, 35, 84, 19]
  )
)






